// 暴力递归 class Solution { public: int minCostClimbingStairs(vector<int>
// &cost) { return min(dfs(0, cost), dfs(1, cost)); }
//     int dfs(int x, vector<int> &cost)
//     {
//         if (x >= cost.size())
//             return 0;
//         return cost[x] + min(dfs(x + 1, cost), dfs(x + 2, cost));
//     }
// };
//

////记忆化搜索
// class Solution
//{
//   public:
//     int minCostClimbingStairs(vector<int> &cost)
//     {
//         int n = cost.size();
//         vector<int>mem(n, -1);
//         return min(dfs(0, cost, mem), dfs(1, cost, mem));
//     }
//     int dfs(int x, vector<int> &cost, vector<int> &mem)
//     {
//         if (x >= cost.size())
//             return 0;
//         if (mem[x] != -1)
//             return mem[x];
//         mem[x] = cost[x] + min(dfs(x + 1, cost, mem), dfs(x + 2, cost, mem));
//         return mem[x];
//     }
// };

//递推
class Solution
{
  public:
    int minCostClimbingStairs(vector<int> &cost)
    {
        int n = cost.size();
        vector<int> dp(n + 1, 0);
        for (int i = 2; i <= n; i++)
        {
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }
};

